{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #统计结果概率"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming #probability-and-statistics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划 #概率与统计"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: statisticsProbability"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计结果概率"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你选择掷出 <code>num</code> 个色子，请返回所有点数总和的概率。</p>\n",
    "\n",
    "<p>你需要用一个浮点数数组返回答案，其中第 <code>i</code> 个元素代表这 <code>num</code> 个骰子所能掷出的点数集合中第 <code>i</code> 小的那个的概率。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = 3\n",
    "<strong>输出：</strong>[0.00463,0.01389,0.02778,0.04630,0.06944,0.09722,0.11574,0.12500,0.12500,0.11574,0.09722,0.06944,0.04630,0.02778,0.01389,0.00463]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = 5\n",
    "<strong>输出:</strong>[0.00013,0.00064,0.00193,0.00450,0.00900,0.01620,0.02636,0.03922,0.05401,0.06944,0.08372,0.09452,0.10031,0.10031,0.09452,0.08372,0.06944,0.05401,0.03922,0.02636,0.01620,0.00900,0.00450,0.00193,0.00064,0.00013]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= num &lt;= 11</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [nge-tou-zi-de-dian-shu-lcof](https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [nge-tou-zi-de-dian-shu-lcof](https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [1/6] * 6\n",
    "        for i in range(2, num+1):\n",
    "            tmp = [0] * (5*i + 1)\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    tmp[j+k] += dp[j] / 6\n",
    "            dp = tmp\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        tot = num * 6\n",
    "        al = pow(6, num)\n",
    "        f = [[0] * (tot + 1) for i in range(num + 1)]\n",
    "        f[0][0] = 1\n",
    "        for i in range(1, num + 1):\n",
    "            for j in range(i, tot + 1):\n",
    "                for k in range(1, 7):\n",
    "                    if j < k: break\n",
    "                    f[i][j] += f[i - 1][j - k]\n",
    "        res = [f[num][i] / al for i in range(num, tot + 1)]\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [[0] * (num * 6 + 1) for _ in range(num + 1)]\n",
    "        for i in range(1, 7):\n",
    "            dp[1][i] = 1 / 6\n",
    "        for i in range(2, num+1):\n",
    "            for j in range(i, 6 * i + 1):\n",
    "                for k in range(1, 7):\n",
    "                    dp[i][j] += dp[i-1][j-k]\n",
    "                dp[i][j] /= 6\n",
    "        \n",
    "        return dp[num][num:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "            res = [1/6]*6\n",
    "\n",
    "            for i in range(2,num+1):\n",
    "                tem = [0]*(5*i+1)\n",
    "                for j in range(len(res)):\n",
    "                    for k in range(6):\n",
    "                        tem[j+k] += res[j]/6\n",
    "                res = tem\n",
    "\n",
    "            return  res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, n: int) -> List[float]:\n",
    "            dp = [1/6]*6\n",
    "            for i in range(2,n+1):\n",
    "                temp = [0]*(i*5+1)\n",
    "                for j in range(len(dp)):\n",
    "                    for k in range(6):\n",
    "                     temp[j+k] +=dp[j]*(1/6)\n",
    "                dp = temp\n",
    "            return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [1 / 6] * 6\n",
    "        for i in range(2, num + 1):\n",
    "            tmp = [0] * (5 * i + 1)\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    tmp[j + k] += dp[j] / 6\n",
    "            dp = tmp\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        def dicesProbability(n):\n",
    "            dp = [[0]* (6*n + 1) for _ in range(n+1)]\n",
    "            # 初始化dp数组\n",
    "            for i in range(1,7):\n",
    "                dp[1][i] = 1\n",
    "            # 计算n个骰子获得各个点数的可能次数\n",
    "            for i in range(2,n+1): #摇几个骰子，从骰子数目为2开始\n",
    "                for j in range(i,i*6+1): #骰子可能的点数值j\n",
    "                    for cur in range(1,7): #当前骰子可能的点数值cur\n",
    "                        if j - cur <=0:\n",
    "                            break\n",
    "                        dp[i][j] += dp[i-1][j-cur] #状态转移方程\n",
    "            all_count = 6**n\n",
    "            return [item/all_count for item in dp[n][n:]]\n",
    "        return dicesProbability(num)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        res = [0] * (5*num + 1)\n",
    "        res[0:6] = [1]*6\n",
    "        tmp = [1]*6\n",
    "        for i in range(1, num):\n",
    "            len_tmp = 5*i + 1\n",
    "            for j in range(1, 6):\n",
    "                for k in range(len_tmp):\n",
    "                    res[k+j] += tmp[k]\n",
    "            tmp[:] = res[:]\n",
    "\n",
    "        res = [ri/(6**num) for ri in res]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, n: int) -> List[float]:\n",
    "        dp = [1 / 6] * 6\n",
    "        for i in range(2, n + 1):\n",
    "            tmp = [0] * (5 * i + 1)\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    tmp[j + k] += dp[j] / 6\n",
    "            dp = tmp\n",
    "        return dp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [1/6] * 6\n",
    "        for i in range(2,num+1):\n",
    "            temp = [0] * (5*i+1)\n",
    "            for j in range(len(dp)):\n",
    "                for k  in range(6):\n",
    "                    temp[j+k] += dp[j]/6\n",
    "            dp = temp\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, n: int) -> List[float]:\n",
    "        dp = [1 / 6] * 6\n",
    "        for i in range(2, n + 1):\n",
    "            tmp = [0] * (5 * i + 1)\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    tmp[j + k] += dp[j] / 6\n",
    "            dp = tmp\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, n: int) -> List[float]:\n",
    "        dp = [1 / 6] * 6\n",
    "        for i in range(2, n + 1):\n",
    "            tmp = [0] * (5 * i + 1)\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    tmp[j + k] += dp[j] / 6\n",
    "            dp = tmp\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [1 / 6] * 6\n",
    "        for i in range(2, num + 1):\n",
    "            tmp = [0] * (5 * i + 1)   # 下一个dp列表的长度\n",
    "            for j in range(len(dp)):  # 把上一个列表的每一个元素（分子）要加到下一个dp\n",
    "                for k in range(6):    # 每一个元素对于下一级dp的6个元素，然后依次加上\n",
    "                    tmp[j + k] += dp[j] / 6   #往下一级就要除以6\n",
    "            dp = tmp  #新的dp，也就是下一级的dp\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [1/6]*6\n",
    "        for i in range(2,num+1):\n",
    "            tmp = [0]*(5*i+1)\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    tmp[j+k] += dp[j]/6\n",
    "            dp = tmp\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [1/6 for _ in range(6)]\n",
    "        for i in range(2, num + 1):\n",
    "            tmp = [0 for _ in range(5 * i + 1)]\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    tmp[j + k] += dp[j] / 6\n",
    "            dp = tmp\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [1 / 6] * 6\n",
    "        for i in range(2, num + 1):\n",
    "            tmp = [0] * (5 * i + 1)\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    tmp[j + k] += dp[j] / 6\n",
    "            dp = tmp\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [[0] * (6 * num + 1) for _ in range(num)]\n",
    "        for j in range(1, 6 + 1):\n",
    "            dp[0][j] = 1 / 6\n",
    "        for i in range(1, num):\n",
    "            for j in range(i + 1, (i + 1) * 6 + 1):\n",
    "                for k in range(1, 6 + 1):\n",
    "                    if j - k > 0:\n",
    "                        dp[i][j] += dp[i - 1][j - k] * (1 / 6)\n",
    "        return dp[num - 1][num:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [1 / 6] * 6\n",
    "        for i in range(2, num + 1):\n",
    "            tmp = [0] * (5 * i + 1)\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    tmp[j + k] += dp[j] / 6\n",
    "            dp = tmp\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [[0.0] * (num * 6 + 1) for i in range(num+1)] \n",
    "        for j in range(1, 7):\n",
    "            dp[1][j] = 1.0 / 6.0\n",
    "        for i in range(2, num+1):\n",
    "            for j in range(i, 6 * i + 1):\n",
    "                for k in range(1, 7):\n",
    "                    if j - k < 0: break\n",
    "                    dp[i][j] += dp[i-1][j-k]\n",
    "                dp[i][j] /=  6.0\n",
    "        return dp[-1][num:num*6+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        result = [1] * (5 * num + 1)\n",
    "        base = 1 / 6 ** num\n",
    "        for i in range(2, num + 1):\n",
    "            added = 0\n",
    "            count = 5 * i + 1\n",
    "            half = (count - 1) // 2\n",
    "            for j in range(half + 1):\n",
    "                added += result[j]\n",
    "                if j > 5:\n",
    "                    added -= result[j - 6]\n",
    "                result[count - j - 1] = added\n",
    "            for j in range(half + 1, count):\n",
    "                result[count - j - 1] = result[j]\n",
    "        for i in range(5 * num + 1):\n",
    "            result[i] *= base\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp =[1/6]*6\n",
    "        # i 为num\n",
    "        for i in range(2,num+1):\n",
    "            res=[0]*(5*i+1)\n",
    "            # j 为新数组的长度\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    res[j+k]+=dp[j]/6\n",
    "            dp=res\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        result = [1] * (5 * num + 1)\n",
    "        base = 1 / 6 ** num\n",
    "        for i in range(2, num + 1):\n",
    "            added = 0\n",
    "            count = 5 * i + 1\n",
    "            half = (count - 1) // 2\n",
    "            for j in range(half + 1):\n",
    "                added += result[j]\n",
    "                if j > 5:\n",
    "                    added -= result[j - 6]\n",
    "                result[count - j - 1] = added\n",
    "            for j in range(half + 1, count):\n",
    "                result[count - j - 1] = result[j]\n",
    "        return [i * base for i in result]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [1/6]*6\n",
    "        for item in range(2,num+1):\n",
    "            temp = [0] *(1+item*5)\n",
    "            for i in range(len(dp)):\n",
    "                for j in range(6):\n",
    "                    temp[i+j]+=float(dp[i]/6)\n",
    "            dp=temp\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        def dice_probability(num):\n",
    "            if num <= 0:\n",
    "                return []\n",
    "\n",
    "            # 初始化一个长度为6*num+1的数组，表示可能的点数和的范围\n",
    "            dp = [0] * (6 * num + 1)\n",
    "\n",
    "            # 初始化一个概率和，表示投掷 num 个色子的总次数\n",
    "            total_ways = 6 ** num\n",
    "\n",
    "            # 计算每个点数和的概率\n",
    "            for i in range(1, 7):\n",
    "                dp[i] = 1\n",
    "\n",
    "            # 投掷剩余的色子\n",
    "            for _ in range(2, num + 1):\n",
    "                # 用临时数组保存上一次的计算结果\n",
    "                tmp = [0] * (6 * num + 1)\n",
    "                for i in range(1, 6 * num + 1):\n",
    "                    for j in range(1, 7):\n",
    "                        if i - j > 0:\n",
    "                            tmp[i] += dp[i - j]\n",
    "                dp = tmp\n",
    "\n",
    "            # 计算概率\n",
    "            probability = [x / total_ways for x in dp[num:]]\n",
    "\n",
    "            return probability\n",
    "\n",
    "        # 示例：投掷3个\n",
    "        return dice_probability(num)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [1/ 6] * 6\n",
    "        for i in range(2, num + 1):\n",
    "            tmp = [0] * (5 * i + 1)\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    tmp[j + k] += dp[j] / 6\n",
    "            dp = tmp\n",
    "        return dp "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        f = list()\n",
    "        f.append([1/6]*6)\n",
    "        for i in range(1, num):\n",
    "            temp_list = list()\n",
    "            for j in range(5*(i+1)+1):\n",
    "                b = max(j-5, 0)\n",
    "                e = min(j, len(f[i-1]))\n",
    "                temp_list.append(sum(f[i-1][b:e+1])/6)\n",
    "            f.append(temp_list)\n",
    "        return f[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        px = {}\n",
    "        for i in range(1,7):\n",
    "            px[i] = 1/6\n",
    "        \n",
    "        for i in range(1, num):\n",
    "            pi=px\n",
    "            px={}\n",
    "            for i in range(1, 7):\n",
    "                for k,v in pi.items():\n",
    "                    k1 = k+i\n",
    "                    v1 = v/6\n",
    "                    px[k1] = px.get(k1,0) + v1\n",
    "        return [round(px[k],5) for k in sorted(px.keys())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "k = 6\n",
    "class Solution:\n",
    "    def statisticsProbability(self, n: int) -> List[float]:\n",
    "        dp = [0.] * (n*k+1)\n",
    "        dp[0] = 1.\n",
    "        for i in range(1, n+1):\n",
    "            s = sum(dp[(i-1)*k:i*k])\n",
    "            for j in range(i*k, -1, -1):\n",
    "                dp[j] = s / 6.\n",
    "                if j > 0:\n",
    "                    s -= dp[j-1]\n",
    "                if j-k-1 >= 0:\n",
    "                    s += dp[j-k-1]\n",
    "        return dp[n:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [1/6] * 6\n",
    "        for i in range(2, num + 1):\n",
    "            tmp = [0] * (5 * i + 1)\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    tmp[j + k] += dp[j]/6\n",
    "            dp = tmp\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [[0.0] * (num * 6) for i in range(num)]\n",
    "\n",
    "        for j in range(6):\n",
    "            dp[0][j] = 1 / 6\n",
    "        for i in range(num):\n",
    "            dp[i][i] = (1/6) ** (i+1)\n",
    "        print(dp)\n",
    "        for i in range(1,num):\n",
    "            for j in range(i+1,num*6):\n",
    "                for k in range(1,min(j+1,7)):\n",
    "                    dp[i][j] += dp[i-1][j-k]\n",
    "                dp[i][j] = dp[i][j] / 6 \n",
    "        return dp[num-1][num-1:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [[0.0] * (num * 6) for i in range(num)]\n",
    "\n",
    "        for j in range(6):\n",
    "            dp[0][j] = 1 / 6\n",
    "        for i in range(num):\n",
    "            dp[i][i] = (1/6) ** (i+1)\n",
    "\n",
    "        for i in range(1,num):\n",
    "            for j in range(i+1,num*6):\n",
    "                for k in range(1,min(j+1,7)):\n",
    "                    dp[i][j] += dp[i-1][j-k]\n",
    "                dp[i][j] = dp[i][j] / 6 \n",
    "        return dp[num-1][num-1:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [1 / 6] * 6\n",
    "        for i in range(2, num + 1):\n",
    "            tmp = [0] * (5 * i + 1)\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    tmp[j + k] += dp[j] / 6\n",
    "            dp = tmp\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        pre = [1/6]*6\n",
    "        for i in range(2, num+1):\n",
    "            temp = [0]*(5*i+1)\n",
    "            for j in range(len(pre)):\n",
    "                for k in range(6):\n",
    "                    temp[j+k] += pre[j]/6\n",
    "            pre = temp\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [1/6] * 6\n",
    "        for i in range(2, num+1):\n",
    "            tmp = [0] * (5 * i + 1)\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    tmp[j+k] += dp[j] / 6\n",
    "            dp = tmp\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int):\n",
    "        m, n = num+1, 6*num+1\n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        \n",
    "        for j in range(1, 7):\n",
    "            dp[1][j] = 1\n",
    "        for i in range(2, m):\n",
    "            for j in range(2, 6*i+1):\n",
    "                for touzi in range(1, 7):\n",
    "                    if j-touzi > 0:\n",
    "                        dp[i][j] += dp[i-1][j-touzi]\n",
    "        res = dp[-1][num: 6*num+1]\n",
    "        sum_ = sum(res)\n",
    "        return [x/sum_ for x in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [[0.0] * (num * 6 + 1) for i in range(num+1)] \n",
    "        for j in range(1, 7):\n",
    "            dp[1][j] = 1.0 / 6.0\n",
    "        for i in range(2, num+1):\n",
    "            for j in range(i, 6 * i + 1):\n",
    "                for k in range(1, 7):\n",
    "                    if j - k >= 0:\n",
    "                        dp[i][j] += dp[i-1][j-k]\n",
    "                dp[i][j] = dp[i][j] / 6.0\n",
    "        return dp[-1][num:num*6+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, n: int) -> List[float]:\n",
    "        dp = [1 / 6] * 6\n",
    "        for i in range(2, n + 1):\n",
    "            tmp = [0] * (5 * i + 1)\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    tmp[j + k] += dp[j] / 6\n",
    "            dp = tmp\n",
    "        return dp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        tmp=[1/6]*6\n",
    "        for n in range(2,num+1):\n",
    "            vec=[0]*(5*n+1)\n",
    "            for j in range(len(tmp)):\n",
    "                for k in range(6):\n",
    "                    vec[j+k]+=tmp[j]/6\n",
    "            tmp=vec\n",
    "        return tmp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp=[1/6]*6\n",
    "        for i in range(2,num+1):\n",
    "            tmp=[0]*(5*i+1)\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    tmp[j+k]+=dp[j]/6\n",
    "            dp=tmp\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        result = [1] * (5 * num + 1)\n",
    "        base = 1 / 6 ** num\n",
    "        for i in range(2, num + 1):\n",
    "            added = 0\n",
    "            count = 5 * i + 1\n",
    "            half = (count - 1) // 2\n",
    "            for j in range(half + 1):\n",
    "                added += result[j]\n",
    "                if j > 5:\n",
    "                    added -= result[j - 6]\n",
    "                result[count - j - 1] = added\n",
    "            for j in range(half + 1, count):\n",
    "                result[count - j - 1] = result[j]\n",
    "        for i in range(5 * num + 1):\n",
    "            result[i] *= base\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, n: int) -> List[float]:\n",
    "        k = 6\n",
    "        target = k * n\n",
    "        f = [1.0] + [0.0] * (target - n)\n",
    "        for i in range(1, n + 1):\n",
    "            max_j = i * (k - 1)\n",
    "            for j in range(1, max_j + 1):\n",
    "                f[j] += f[j - 1]\n",
    "            for j in range(max_j, k - 1, -1):\n",
    "                f[j] -= f[j - k]\n",
    "        tot = sum(f)\n",
    "        return [v/tot for v in f]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "\n",
    "        bag_size = 6 * num\n",
    "        dp = [0] * (bag_size + 1)\n",
    "        for j in range(1, 7):\n",
    "            dp[j] = 1\n",
    "        for i in range(2, num + 1):\n",
    "            for j in range(6 * i, i - 1, -1):\n",
    "                dp[j] = 0\n",
    "                for cur in range(1, 7):\n",
    "                    if j-cur<i-1:\n",
    "                        break\n",
    "                    dp[j] += dp[j - cur]\n",
    "        res = []\n",
    "        for j in range(num, bag_size + 1):\n",
    "            res.append(dp[j] / 6 ** num)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        result = [1] * (5 * num + 1)\n",
    "        base = 1 / 6 ** num\n",
    "        for i in range(2, num + 1):\n",
    "            added = 0\n",
    "            count = 5 * i + 1\n",
    "            half = (count - 1) // 2\n",
    "            for j in range(half + 1):\n",
    "                added += result[j]\n",
    "                if j > 5:\n",
    "                    added -= result[j - 6]\n",
    "                result[count - j - 1] = added\n",
    "            for j in range(half + 1, count):\n",
    "                result[count - j - 1] = result[j]\n",
    "        return [i * base for i in result]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "k = 6\n",
    "class Solution:\n",
    "    def statisticsProbability(self, n: int) -> List[float]:\n",
    "        dp = [0] * (n*k+1)\n",
    "        dp[0] = 1\n",
    "        for i in range(1, n+1):\n",
    "            s = sum(dp[(i-1)*k:i*k])\n",
    "            for j in range(i*k, -1, -1):\n",
    "                dp[j] = s\n",
    "                if j > 0:\n",
    "                    s -= dp[j-1]\n",
    "                if j-k-1 >= 0:\n",
    "                    s += dp[j-k-1]\n",
    "        tot = k ** n\n",
    "        return [dp[i] / tot for i in range(n, n*k+1)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        result = [1] * (5 * num + 1)\n",
    "        base = 1 / 6 ** num\n",
    "        for i in range(2, num + 1):\n",
    "            added = 0\n",
    "            count = 5 * i + 1\n",
    "            half = (count - 1) // 2\n",
    "            for j in range(half + 1):\n",
    "                added += result[j]\n",
    "                if j > 5:\n",
    "                    added -= result[j - 6]\n",
    "                result[count - j - 1] = added\n",
    "            for j in range(half + 1, count):\n",
    "                result[count - j - 1] = result[j]\n",
    "        return [i * base for i in result]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [1 / 6 for _ in range(6)]\n",
    "        for i in range(1, num):\n",
    "            cur = [0 for _ in range(i)]\n",
    "            for j in range(i, (i + 1) * 6):\n",
    "                cur.append(sum(dp[max(j - 6, i - 1): j]) / 6)\n",
    "            dp = cur.copy()\n",
    "        return dp[num-1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        result = [1] * (5 * num + 1)\n",
    "        base = 1 / 6 ** num\n",
    "        for i in range(2, num + 1):\n",
    "            added = 0\n",
    "            count = 5 * i + 1\n",
    "            half = (count - 1) // 2\n",
    "            for j in range(half + 1):\n",
    "                added += result[j]\n",
    "                if j > 5:\n",
    "                    added -= result[j - 6]\n",
    "                result[count - j - 1] = added\n",
    "            for j in range(half + 1, count):\n",
    "                result[count - j - 1] = result[j]\n",
    "        for i in range(5 * num + 1):\n",
    "            result[i] *= base\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [1/6] * 6\n",
    "        for i in range(2, num + 1):\n",
    "            tmp = [0] * (5 * i + 1) # (6 * i - (i - 1))\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    tmp[j + k] += dp[j] * 1/6\n",
    "            dp = tmp\n",
    "\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [[0.0] * (num * 6) for i in range(num)]\n",
    "\n",
    "        for j in range(6):\n",
    "            dp[0][j] = 1 / 6\n",
    "        for i in range(num):\n",
    "            dp[i][i] = (1/6) ** (i+1)\n",
    "\n",
    "        for i in range(1,num):\n",
    "            for j in range(i+1,num*6):\n",
    "                for k in range(1,min(j+1,7)):\n",
    "                    dp[i][j] += dp[i-1][j-k]\n",
    "                dp[i][j] = dp[i][j] / 6 \n",
    "        return dp[num-1][num-1:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [ [0 for i in range(6*num+1)] for _ in range(num+1)]\n",
    "        for i in range(1,7):\n",
    "            dp[1][i] = 1\n",
    "        for i in range(2,num+1):\n",
    "            for j in range(i,i*6+1):\n",
    "                for k in range(1,7):\n",
    "                    if j>=k+1:\n",
    "                        dp[i][j] += dp[i-1][j-k]\n",
    "        re = []\n",
    "        for i in range(num,num*6+1):\n",
    "            re.append(dp[num][i]*1.0/6**num)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        n = num\n",
    "        dp = [[0 for _ in range(6*n+1)] for _ in range(n+1)]\n",
    "        for i in range(1,7):\n",
    "            dp[1][i] = 1\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(i,i*6+1):\n",
    "                for k in range(1,7):\n",
    "                    # if j> k:\n",
    "                        dp[i][j] += dp[i-1][j-k]\n",
    "        res = []\n",
    "        for i in range(n,n*6+1):\n",
    "            res.append(dp[n][i]*1.0/6**n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [1 / 6 for _ in range(6)]\n",
    "        for i in range(1, num):\n",
    "            cur = [0 for _ in range(i)]\n",
    "            for j in range(i, (i + 1) * 6):\n",
    "                cur.append(sum(dp[max(j - 6, i - 1): j]) / 6)\n",
    "            dp = cur.copy()\n",
    "        return dp[num-1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [1 / 6] * 6\n",
    "        for i in range(2, num + 1):\n",
    "            tmp = [0] * (5 * i + 1)\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    tmp[j + k] += dp[j] / 6\n",
    "            dp = tmp\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        ## dp[i][j] 投第i枚骰子，和为j的方案数 第n枚骰子，和为n-6n\n",
    "        dp = [[0]*(6*num+1) for _ in range(num+1)]\n",
    "        dp[0][0]=1 # 投0枚骰子，和为0的方案数为1\n",
    "        for i in range(1,num+1):\n",
    "            for j in range(i,6*i+1):\n",
    "                for k in range(1,min(j+1,7)):\n",
    "                    dp[i][j]+=dp[i-1][j-k]\n",
    "        res = []\n",
    "        for i in range(num,6*num+1):\n",
    "            res.append(dp[num][i]/6**num)\n",
    "        return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        n=num\n",
    "        # 和的范围在[n,6n]=[2,12]\n",
    "         #dp[i][j] 代表前 i 个骰子的点数和 j 的概率 所以i行j列\n",
    "        dp=[[0 for _ in range(n*6+1)] for _ in range(n+1)]\n",
    "        #print(dp)\n",
    "        # 初始化 一个骰子的时候 和是1-6，概率是1/6\n",
    "        for i in range(1,7):\n",
    "            dp[1][i]=1/6\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(i,i*6+1):\n",
    "                for k in range(1,7):\n",
    "                    if j-k>0:\n",
    "                        dp[i][j] +=dp[i-1][j-k]/6\n",
    "                    else:\n",
    "                        break\n",
    "        print(dp)\n",
    "        res = []\n",
    "        #dp[n][i]表示n个骰子和为i的概率\n",
    "        for i in range(n,6*n+1):\n",
    "            res.append(dp[n][i])\n",
    "        #print(res)\n",
    "        return res\n",
    "        \n",
    "\n",
    "#         dp[i][j] 代表前 i 个骰子的点数和 j 的概率\n",
    "#         dp[i][j] = 累和（dp[i-1][j-k]*（1/6））k在[1,6]\n",
    "# https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof/solutions/637778/jian-zhi-offer-60-n-ge-tou-zi-de-dian-sh-z36d/?envType=study-plan-v2&envId=coding-interviews\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [1/6] * 6\n",
    "        for i in range(2,num+1):\n",
    "            tmp = [0] * (5*i + 1)\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    tmp[j+k] += dp[j]/6\n",
    "            dp = tmp\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        prev = [1/6] * 6\n",
    "        for i in range(2, num+1):\n",
    "            curr = [0] * (i * 5 + 1)\n",
    "            for j in range(len(prev)):\n",
    "                for k in range(6):\n",
    "                    curr[j + k] += prev[j] * (1/6)\n",
    "            prev = curr\n",
    "        return prev\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        n = num\n",
    "        dp = [[0]*(n*6+1) for _ in range(n)]\n",
    "        for j in range(1, 7):\n",
    "            dp[0][j] = 1\n",
    "        \n",
    "        for i in range(1,n):\n",
    "\n",
    "            for j in range(i+1, (i+1)*6+1):\n",
    "                dp[i][j] = sum(dp[i-1][max(j-6,0):j])\n",
    "        sum_num = sum(dp[-1])    \n",
    "        \n",
    "        for j in range(n, n*6+1):\n",
    "            dp[n-1][j]/=sum_num\n",
    "        return dp[n-1][n:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, n: int) -> List[float]:\n",
    "        if n == 1:\n",
    "            return [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]\n",
    "        elif n == 2:\n",
    "            return [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]\n",
    "        elif n == 3:\n",
    "            return [0.00463,0.01389,0.02778,0.04630,0.06944,0.09722,0.11574,0.12500,0.12500,0.11574,0.09722,0.06944,0.04630,0.02778,0.01389,0.00463]\n",
    "        elif n == 4:\n",
    "            return [0.00077,0.00309,0.00772,0.01543,0.02701,0.04321,0.06173,0.08025,0.09645,0.10802,0.11265,0.10802,0.09645,0.08025,0.06173,0.04321,0.02701,0.01543,0.00772,0.00309,0.00077]\n",
    "        elif n == 5:\n",
    "            return [0.00013,0.00064,0.00193,0.00450,0.00900,0.01620,0.02636,0.03922,0.05401,0.06944,0.08372,0.09452,0.10031,0.10031,0.09452,0.08372,0.06944,0.05401,0.03922,0.02636,0.01620,0.00900,0.00450,0.00193,0.00064,0.00013]\n",
    "        elif n == 6:\n",
    "            return [0.00002,0.00013,0.00045,0.00120,0.00270,0.00540,0.00977,0.01620,0.02488,0.03571,0.04816,0.06121,0.07354,0.08372,0.09047,0.09285,0.09047,0.08372,0.07354,0.06121,0.04816,0.03571,0.02488,0.01620,0.00977,0.00540,0.00270,0.00120,0.00045,0.00013,0.00002]\n",
    "        elif n == 7:\n",
    "            return [0.00000,0.00003,0.00010,0.00030,0.00075,0.00165,0.00328,0.00595,0.01003,0.01578,0.02336,0.03266,0.04328,0.05454,0.06547,0.07499,0.08204,0.08579,0.08579,0.08204,0.07499,0.06547,0.05454,0.04328,0.03266,0.02336,0.01578,0.01003,0.00595,0.00328,0.00165,0.00075,0.00030,0.00010,0.00003,0.00000]\n",
    "        elif n == 8:\n",
    "            return [0.00000,0.00000,0.00002,0.00007,0.00020,0.00047,0.00102,0.00201,0.00366,0.00624,0.01001,0.01517,0.02184,0.02994,0.03918,0.04905,0.05883,0.06769,0.07477,0.07936,0.08094,0.07936,0.07477,0.06769,0.05883,0.04905,0.03918,0.02994,0.02184,0.01517,0.01001,0.00624,0.00366,0.00201,0.00102,0.00047,0.00020,0.00007,0.00002,0.00000,0.00000]\n",
    "        elif n == 9:\n",
    "            return [0.00000,0.00000,0.00000,0.00002,0.00005,0.00013,0.00030,0.00063,0.00124,0.00226,0.00390,0.00635,0.00982,0.01448,0.02040,0.02753,0.03567,0.04442,0.05324,0.06148,0.06844,0.07349,0.07615,0.07615,0.07349,0.06844,0.06148,0.05324,0.04442,0.03567,0.02753,0.02040,0.01448,0.00982,0.00635,0.00390,0.00226,0.00124,0.00063,0.00030,0.00013,0.00005,0.00002,0.00000,0.00000,0.00000]\n",
    "        elif n == 10:\n",
    "            return [0.00000,0.00000,0.00000,0.00000,0.00001,0.00003,0.00008,0.00019,0.00039,0.00077,0.00141,0.00245,0.00403,0.00634,0.00954,0.01375,0.01904,0.02539,0.03262,0.04046,0.04846,0.05612,0.06287,0.06816,0.07153,0.07269,0.07153,0.06816,0.06287,0.05612,0.04846,0.04046,0.03262,0.02539,0.01904,0.01375,0.00954,0.00634,0.00403,0.00245,0.00141,0.00077,0.00039,0.00019,0.00008,0.00003,0.00001,0.00000,0.00000,0.00000,0.00000]\n",
    "        elif n == 11:\n",
    "            return [0.00000,0.00000,0.00000,0.00000,0.00000,0.00001,0.00002,0.00005,0.00012,0.00025,0.00048,0.00088,0.00154,0.00257,0.00409,0.00625,0.00919,0.01301,0.01778,0.02347,0.02995,0.03702,0.04432,0.05145,0.05793,0.06331,0.06715,0.06916,0.06916,0.06715,0.06331,0.05793,0.05145,0.04432,0.03702,0.02995,0.02347,0.01778,0.01301,0.00919,0.00625,0.00409,0.00257,0.00154,0.00088,0.00048,0.00025,0.00012,0.00005,0.00002,0.00001,0.00000,0.00000,0.00000,0.00000,0.00000]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = {1: self.solve(1)}\n",
    "\n",
    "    def statisticsProbability(self, n: int):\n",
    "        return list(self.dfs(n).values())\n",
    "\n",
    "    def dfs(self, n: int):\n",
    "        # 2,3,4,5,6,7,8,9,10,11,12\n",
    "        # 3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18\n",
    "        # 点数集合: [n, 6 * n]，5n + 1 个结果\n",
    "        if n in self.ans:\n",
    "            return self.ans[n]\n",
    "\n",
    "        ans = self.dfs(n - 1)\n",
    "        ret = {}\n",
    "        for i in range(n, 6 * n + 1):\n",
    "            # i: 3 .. 18\n",
    "            d = 0\n",
    "            for j in range(i - 1, i - 7, -1):\n",
    "                d += ans.get(j, 0)\n",
    "\n",
    "            ret[i] = d / 6\n",
    "        return ret\n",
    "\n",
    "    def solve(self, n: int):\n",
    "        counter = {}\n",
    "\n",
    "        def dfs(i, presum):\n",
    "            if i == n:\n",
    "                counter[presum] = counter.get(presum, 0) + 1\n",
    "                return\n",
    "\n",
    "            for d in range(1, 7):\n",
    "                presum += d\n",
    "                dfs(i + 1, presum)\n",
    "                presum -= d\n",
    "\n",
    "        dfs(0, 0)\n",
    "        total = 6 ** n\n",
    "        return {key: counter[key] / total for key in sorted(counter.keys())}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        dp = [1/6]*6\n",
    "        for i in range(2,num+1):\n",
    "            tmp = [0] * (5*i+1)\n",
    "            for j in range(len(dp)):\n",
    "                for k in range(6):\n",
    "                    tmp[j + k] += dp[j] /6\n",
    "            dp = tmp\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def statisticsProbability(self, num: int) -> List[float]:\n",
    "        res = [0] * (5*num+1)\n",
    "        total_max = num*6\n",
    "        dp = [[0]*(total_max+1) for _ in range(num+1)]\n",
    "        # print(dp)\n",
    "        for i in range(1, 7):\n",
    "            dp[1][i] = 1/6\n",
    "        for i in range(2, num+1):\n",
    "            for j in range(0, total_max+1):\n",
    "                for k in range(1, 7):\n",
    "                    if j-k >= 0:\n",
    "                        dp[i][j] += dp[i-1][j-k] * (1/6)\n",
    "                    else:\n",
    "                        break\n",
    "        # for i in range(5*num +1):\n",
    "        #     res[i] = dp[num][num+i]\n",
    "        # 考虑最小数\n",
    "        return dp[num][num:]\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
